package _17_剑指Offer;

public class _46_剑指Offer把数字翻译成字符串 {

    public static void main(String[] args) {

        _46_剑指Offer把数字翻译成字符串 v = new _46_剑指Offer把数字翻译成字符串();
        int nums = 1;
        System.out.println(v.translateNum(nums));

    }

    public int translateNum(int num) {
        char[] chars = String.valueOf(num).toCharArray();
        int first = 1;
        int second = 1;
        for (int i = 2; i <= chars.length; i++) {
            int n = (chars[i - 2] - '0') * 10 + (chars[i - 1] - '0');
            if (n >= 10 && n <= 25) {
                second = first + second;
                first = second - first;
            } else {
                first = second;
            }
        }
        return second;
    }

    // 减低空间复杂度
    public int translateNum1(int num) {
        char[] chars = String.valueOf(num).toCharArray();
        int[] dp = new int[chars.length + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= chars.length; i++) {
            int n = (chars[i - 2] - '0') * 10 + (chars[i - 1] - '0');
            if (n >= 10 && n <= 25) {
                dp[i] = dp[i - 1] + dp[i - 2];
            } else {
                dp[i] = dp[i - 1];
            }
        }
        return dp[chars.length];
    }

}
